﻿/*
//复写零-复习
class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int cur=0,des=-1,n=arr.size();
        while(1){
            if(arr[cur]) des++;
            else des+=2;
            if(des>=n-1) break;
            cur++;
        }
        if(des==n){
            arr[--des]=0;
            cur--;
            des--;
        }
        while(cur>=0) {
            if(arr[cur]) arr[des]=arr[cur];
            else {
                arr[des--]=0;
                arr[des]=0;
            }
            des--;
            cur--;
        }
    }
};


//快乐数
class Solution {
public:
    int RetSum(int num) {
        int tmp=0,sum=0;
        while(num){
            tmp=num%10;
            sum+=tmp*tmp;
            num/=10;
        }
        return sum;
    }
    bool isHappy(int n) {
        int slow=RetSum(n);
        int fast=RetSum(RetSum(n));
        while(slow!=fast) {
            slow=RetSum(slow);
            fast=RetSum(RetSum(fast));
        }
        if(slow==1) return true;
        return false;
    }
};
//注意：这里利用了环形链表的原理（环形链表查找链表入口时，应先查找快慢指针相遇点，
//再分别让两个指针从起点和相遇点以相同的速度同时出发，相遇即是入口）


//盛水最多的容器
class Solution {
public:
    int maxArea(vector<int>& height) {
        int left=0,right=height.size()-1,MaxA=0;
        while(left<right) {
            if(height[left]<height[right]) {
                int tmp=height[left]*(right-left);
                MaxA=max(MaxA,tmp);
                left++;
            }
            else{
                int tmp=height[right]*(right-left);
                MaxA=max(MaxA,tmp);
                right--;
            }
        }
        return MaxA;
    }
};


//有效的三角形个数
class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int count = 0,target=0,left=0,right=0,sum=0;
        for (int i = nums.size() - 1; i >= 0; i--) {
            target = nums[i];
            left = 0, right = i-1;
            while (left < right) {
                sum = nums[left] + nums[right];
                if (sum > target) {
                    count += right - left;
                    right--;
                }
                else{
                    left++;
                }
            }
        }
        return count;
    }
};


//找到总价值为目标值的两个商品
class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) {
        int left=0,right=price.size()-1,sum=0;
        while(left<right) {
            sum=price[left]+price[right];
            if(sum>target) right--;
            else if(sum<target) left++;
            else return {price[left],price[right]};
        }
        return {-1,-1};
    }
};


//三数之和
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret;
        int left = 0, right = 0, sum = 0, k = 0;
        sort(nums.begin(), nums.end());
        for (int i = nums.size() - 1; i >= 0;) {
            left = 0, right = i - 1;
            k = -nums[i];
            while (left < right) {
                sum = nums[left] + nums[right];
                if (sum > k) right--;
                else if (sum < k) left++;
                else {
                    ret.push_back({nums[left], nums[right], nums[i]});
                    left++,right--;
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    while (left < right && nums[right] == nums[right + 1]) right--;
                }
            }
            i--;
            while (i >= 0 && nums[i] == nums[i + 1]) i--;
        }
        return ret;
    }
};
*/
